package com.al.study.record.search;

import com.al.study.record.sort.InsertSort;

/**
 * Created by yuxi on 2017/9/1.
 */
public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {-2, 1, 33, 4, 5, 0, 0, -1, 45, 908, 3};

        //先排序
        int[] insertSort = InsertSort.insertSort(arr);

        //二分查询
        int result1 = binarySearch(insertSort, 5);
        int result2 = binarySearchTwo(insertSort, 0, insertSort.length, 5);
        System.out.println(result1 == result2);
    }

    /**
     * 二分查找【非递归实现】
     *
     * @param insertSort 排完序的数组
     * @param key        需要查找的key
     * @return
     */
    private static int binarySearch(int[] insertSort, int key) {
        if (insertSort.length == 0) return -1;
        int low = 0;
        int high = insertSort.length - 1;
        while (low <= high) {
            int mid = (high + low) / 2;
            if (insertSort[mid] == key) {
                return mid;
            } else if (insertSort[mid] < key) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }


    /**
     * 二分查找【递归实现】
     *
     * @param insertSort 排完序的数组
     * @param key        需要查找的key
     * @return
     */
    private static int binarySearchTwo(int[] insertSort, int low, int high, int key) {
        if (low > high) return -1;
        int mid = (high + low) / 2;
        if (insertSort[mid] == key) return mid;
        else if (insertSort[mid] < key) {
            return binarySearchTwo(insertSort, mid + 1, high, key);
        } else {
            return binarySearchTwo(insertSort, low, mid - 1, key);
        }
    }
}
